<html><!-- Created using the cpp_pretty_printer from the dlib C++ library.  See http://dlib.net for updates. --><head><title>dlib C++ Library - max_cost_assignment_ex.cpp</title></head><body bgcolor='white'><pre>
<font color='#009900'>// The contents of this file are in the public domain. See LICENSE_FOR_EXAMPLE_PROGRAMS.txt
</font><font color='#009900'>/*
 
 This simple example shows how to call dlib's optimal linear assignment problem solver.
 It is an implementation of the famous Hungarian algorithm and is quite fast, operating in
 O(N^3) time.

*/</font>

<font color='#0000FF'>#include</font> <font color='#5555FF'>&lt;</font>dlib<font color='#5555FF'>/</font>optimization<font color='#5555FF'>/</font>max_cost_assignment.h<font color='#5555FF'>&gt;</font>
<font color='#0000FF'>#include</font> <font color='#5555FF'>&lt;</font>iostream<font color='#5555FF'>&gt;</font>

<font color='#0000FF'>using</font> <font color='#0000FF'>namespace</font> std;
<font color='#0000FF'>using</font> <font color='#0000FF'>namespace</font> dlib;

<font color='#0000FF'><u>int</u></font> <b><a name='main'></a>main</b> <font face='Lucida Console'>(</font><font face='Lucida Console'>)</font>
<b>{</b>
    <font color='#009900'>// Let's imagine you need to assign N people to N jobs.  Additionally, each person will make
</font>    <font color='#009900'>// your company a certain amount of money at each job, but each person has different skills
</font>    <font color='#009900'>// so they are better at some jobs and worse at others.  You would like to find the best way
</font>    <font color='#009900'>// to assign people to these jobs.  In particular, you would like to maximize the amount of
</font>    <font color='#009900'>// money the group makes as a whole.  This is an example of an assignment problem and is
</font>    <font color='#009900'>// what is solved by the max_cost_assignment() routine.
</font>    <font color='#009900'>// 
</font>    <font color='#009900'>// So in this example, let's imagine we have 3 people and 3 jobs.  We represent the amount of
</font>    <font color='#009900'>// money each person will produce at each job with a cost matrix.  Each row corresponds to a
</font>    <font color='#009900'>// person and each column corresponds to a job.  So for example, below we are saying that
</font>    <font color='#009900'>// person 0 will make $1 at job 0, $2 at job 1, and $6 at job 2.  
</font>    matrix<font color='#5555FF'>&lt;</font><font color='#0000FF'><u>int</u></font><font color='#5555FF'>&gt;</font> <font color='#BB00BB'>cost</font><font face='Lucida Console'>(</font><font color='#979000'>3</font>,<font color='#979000'>3</font><font face='Lucida Console'>)</font>;
    cost <font color='#5555FF'>=</font> <font color='#979000'>1</font>, <font color='#979000'>2</font>, <font color='#979000'>6</font>,
           <font color='#979000'>5</font>, <font color='#979000'>3</font>, <font color='#979000'>6</font>,
           <font color='#979000'>4</font>, <font color='#979000'>5</font>, <font color='#979000'>0</font>;

    <font color='#009900'>// To find out the best assignment of people to jobs we just need to call this function.
</font>    std::vector<font color='#5555FF'>&lt;</font><font color='#0000FF'><u>long</u></font><font color='#5555FF'>&gt;</font> assignment <font color='#5555FF'>=</font> <font color='#BB00BB'>max_cost_assignment</font><font face='Lucida Console'>(</font>cost<font face='Lucida Console'>)</font>;

    <font color='#009900'>// This prints optimal assignments:  [2, 0, 1] which indicates that we should assign
</font>    <font color='#009900'>// the person from the first row of the cost matrix to job 2, the middle row person to
</font>    <font color='#009900'>// job 0, and the bottom row person to job 1.
</font>    <font color='#0000FF'>for</font> <font face='Lucida Console'>(</font><font color='#0000FF'><u>unsigned</u></font> <font color='#0000FF'><u>int</u></font> i <font color='#5555FF'>=</font> <font color='#979000'>0</font>; i <font color='#5555FF'>&lt;</font> assignment.<font color='#BB00BB'>size</font><font face='Lucida Console'>(</font><font face='Lucida Console'>)</font>; i<font color='#5555FF'>+</font><font color='#5555FF'>+</font><font face='Lucida Console'>)</font>
        cout <font color='#5555FF'>&lt;</font><font color='#5555FF'>&lt;</font> assignment[i] <font color='#5555FF'>&lt;</font><font color='#5555FF'>&lt;</font> std::endl;

    <font color='#009900'>// This prints optimal cost:  16.0
</font>    <font color='#009900'>// which is correct since our optimal assignment is 6+5+5.
</font>    cout <font color='#5555FF'>&lt;</font><font color='#5555FF'>&lt;</font> "<font color='#CC0000'>optimal cost: </font>" <font color='#5555FF'>&lt;</font><font color='#5555FF'>&lt;</font> <font color='#BB00BB'>assignment_cost</font><font face='Lucida Console'>(</font>cost, assignment<font face='Lucida Console'>)</font> <font color='#5555FF'>&lt;</font><font color='#5555FF'>&lt;</font> endl;
<b>}</b>


</pre></body></html>